package com.leetcode.algorithm.y22.m07.w5;

import com.leetcode.algorithm.common.ListNode;

/**
 * 328. 奇偶链表
 * 
 * https://leetcode.cn/problems/odd-even-linked-list/
 * 
 * @author jie.deng
 *
 */
class Question0328Solution01 {
	
	public ListNode oddEvenList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode evenTail = head;
		ListNode oddHead = head.next;
		ListNode oddTail = oddHead;
		ListNode cur = oddHead;
		boolean evenFlag = true;
		while (cur.next != null) {
			cur = cur.next;
			if (evenFlag) {
				evenTail.next = cur;
				evenTail = cur;
			} else {
				oddTail.next = cur;
				oddTail = cur;
			}
			evenFlag = !evenFlag;
		}
		evenTail.next = oddHead;
		oddTail.next = null;
		return head;
	}
    
}